#include <cstdio>
#include<iostream>
#include<stdio.h>
#include <string.h>
#include<string>
using namespace std;
const int N=15,M=1010;
int dp[N][N];
char str[M][N];
int distance(char s1[],char s2[])
{
    int a=strlen(s1);
    int b=strlen(s2);
    for(int i=1;i<=a;i++)dp[i][0]=i;
    for(int i=1;i<=b;i++)dp[0][i]=i;
    for(int i=1;i<=a;i++)
    {
        for(int j=1;j<=b;j++)
        {
            if(s1[i]==s2[j])dp[i][j]=dp[i-1][j-1];
            else dp[i][j]=min(dp[i][j-1]+1,min(dp[i-1][j]+1,dp[i-1][j-1]+1));
        }
    }
    return dp[a][b];
}
int main()
{
    int n=0,m;
    cin>>n>>m;
    for(int i=0;i<n;i++)scanf("%s",str[i]+1);
    while(m--)
    {
        char s[N];
        int limit=0;
        scanf("%s%d",s+1,&limit);
        int res=0;
        for(int i=0;i<n;i++)
            {
                if(distance(str[i],s)<=limit)
                    res++;
            }
        cout<<res<<endl;
    }
    
}